#include <stack>
#include <vector>
using namespace std;
int largestRectangleArea(vector<int> &heights) {
  stack<int> stk;
  heights.push_back(-1);
  int res = -1;
  for (int i = 0; i < heights.size(); i++) {
    if (!stk.empty() && heights[i] < heights[stk.top()]) {
      // 栈顶元素找到右侧最小是值
      int idx = stk.top();
      stk.pop();
      // 左侧最小值
      int left = stk.empty() ? -1 : stk.top();
      // 计算面积
      res = max(res, (idx - left - 1) * heights[idx]);
    }
    stk.push(i);
  }
  return res;
}